package com.lik.javadeep.basic.sort;

public class InsertionSort {
    public static void main(String[] args) {
        int[] ints = {9, 3, 5, 2, 9, 6, 18};
        insertionSort(ints);

        for (int i : ints) {
            System.out.println(i);
        }

    }

    private static void insertionSort(int[] ints) {
        // 当前要做操作的元素
        // 备份
        int back;

        // 数组分为 sorted target unsorted ；
        // 以targetIndex 为分界（targetIndex 即为sorted 区域的长度）
        for (int targetIndex = 0; targetIndex < ints.length - 1; targetIndex++) {

            back = ints[targetIndex];

            int foundPlace = findInsertIndex(ints, targetIndex);
            // 将从foundPlace 到targetIndex，右移
            moveRight(ints, foundPlace, targetIndex);

            ints[foundPlace] = back;

        }

    }

    /**
     * 从[0,targetIndex)寻找插入位置
     *
     * @param array
     * @param targetIndex
     * @return
     */
    private static int findInsertIndex(int[] array, int targetIndex) {
        int back = array[targetIndex];
        for (int i = 0; i < targetIndex; i++) {
            if (back < array[i]) {
                return i;
            }
        }

        return targetIndex;
    }

    /**
     * [foundPlace,targetIndex)，右移
     */
    private static void moveRight(int[] array, int foundPlace, int targetIndex) {
        for (int i = targetIndex; i > foundPlace; i--) {
            array[i] = array[i - 1];
        }
    }
}
